package com.leetcode.algorithm.y22.m09.w3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 107. 二叉树的层序遍历 II
 * 
 * https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
 * 
 * @author jie.deng
 *
 */
class Question0107Solution01 {
	
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		// 广度优先搜索，使用队列实现，先进先出
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			// 当前层次结点个数
			int size = queue.size();
			// 遍历当前层
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				// 遍历当前结点
				levelList.add(node.val);
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			list.add(levelList);
		}

		Collections.reverse(list);
		return list;
	}
    
}